# 15.三数之和
# 给你一个整数数组nums ，判断是否存在三元组[nums[i], nums[j], nums[k]]满足i != j、i != k且
# j != k ，同时还满足nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为0且不重复的三元组。
# 注意：答案中不可以包含重复的三元组。
#
# 示例1：
# 输入：nums = [-1, 0, 1, 2, -1, -4]
# 输出：[[-1, -1, 2], [-1, 0, 1]]
# 解释：
# nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
# nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
# nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
# 不同的三元组是[-1, 0, 1]和[-1, -1, 2] 。
# 注意，输出的顺序和三元组的顺序并不重要。
#
# 示例2：
# 输入：nums = [0, 1, 1]
# 输出：[]
# 解释：唯一可能的三元组和不为0 。
#
# 示例3：
# 输入：nums = [0, 0, 0]
# 输出：[[0, 0, 0]]
# 解释：唯一可能的三元组和为0

class Solution:
    def threeSum(self, nums):
        long = len(nums)
        res = []
        nums.sort()
        for i in range(long):
            if i == long - 2:
                break
            left = i + 1
            right = long - 1
            while left < right:
                if nums[i] + nums[left] + nums[right] > 0:
                    right -= 1
                elif nums[i] + nums[left] + nums[right] < 0:
                    left += 1
                else:
                    tmp = [nums[i], nums[left], nums[right]]
                    tmp.sort()
                    if tmp not in res:
                        res.append(tmp)
                    left += 1

        return res

if __name__ == '__main__':
    nums = [-1, 0, 1, 2, -1, -4]
    nums = [0, 1, 1]
    nums = [0, 0, 0,0]
    nums = [-2, 0, 1, 1, 2]
    tmp = Solution()
    res = tmp.threeSum(nums)
    print(res)
    # 这个双指针的方法真的是妙啊，以及最后我自己这个left += 1,很灵性，当然执行用时有点长，这个另说
